1. Field of the Invention
This invention relates generally to an apparatus and method for decoding a stream of input codewords in a high speed data transmission system. More particularly, this invention relates to an apparatus and method for decoding an input stream of variable-length encoded codewords by the use multi-layered parallel processing decoding system to expedite the decoding process while reduce the data storage memory requirement.
2. Description of the Prior Art
The speed of decoding and the complexity of the decoding devices utilized to perform the task of real-time high-speed decoding are two major concerns in the development and application of modern communication and computer technology. As larger volume of data, often in the form of binary bits, are being electronically transmitted, stored and later retrieved, these binary bits are often encoded, i.e., compressed into codewords, for the purposes of accelerating the speed of transmission and for saving the memory space for data storage. These encoded codewords must often be decoded, i.e., decompressed into their original full-length bit strings, either for display or to be further processed. The decoding tasks can be very complicate especially in the case when the a variable length decoding has to be performed when the original bit streams are being encoded into codewords of variable lengths. The complexity arises due to the facts that since each codeword has no fixed length, a decoder must determine not only the codewords but also the determination must be made without first knowing the length of each codeword.
Variable length coding is a technique often applied for lossless data compression wherein a plurality of fixed-length data are converted into codewords of variable lengths. In general, the lengths of the codewords are chosen so that the shorter codewords are used to represent the more frequently occurring data. By properly assigning the variable length codewords to the library for all the possible combinations of codewords, very efficient encoding and decoding processes can be achieved. Huffman coding technique is the most well known and commonly used method to construct a minimum redundant variable length code as a lookup table for encoding and decoding. For that reason, an effective decoding technique which is capable of achieving the processing time-saving for a decoder and to reduce the memory requirements and circuit complexity become very important in the development and application of modern communication and computer technology.
The most straightforward way of carrying out the task of variable length decoding is by the use of a serial variable length decoding method. It examines one bit at a time for determining if a codeword is found. One more bit is added to the bit string if the examined bit-string does not constitute a codeword according to a codeword table. This process is repeated one bit at a time until a codeword is found. Then the same process is performed for next following codeword. This process is simple and straightforward but is too slow to meet the high speed real-time requirement.
A parallel variable length decoder may be used to increase the speed of the decoding process. The decoder is designed to comprise a table in its read only memory (ROM) which contains all the symbols for the codewords to be determined. The decoder then read M-bit from the input bit stream where M is the maximum codeword length. This M-bit input string is then compared with each word in the symbol table. Since, the fixed length bit-string read from the input data stream equals to the maximum codeword length, the actual codeword length information as found is used to define the beginning point of next following codeword in the input data stream. This method has the disadvantage that when the maximum codeword length, i.e., M, is a large number, then the symbol table which has a table length of 2.sup.M in the read only memory (ROM) may become too big and occupy too much memory space. The original purpose of saving data storage space by the use of encoding techniques may be defeated when the symbol exceeds a certain limit.
Frank discloses in U.S. Pat. 3,883,847 entitled "Uniform Decoding of Minimum Redundancy Codes" (Issued on May 13, 1975) an apparatus for decoding an ordered sequence of variable length input binary codewords each of these codewords is associated with a symbol in an N-symbol alphabet table. The apparatus receives a fixed-length sample of an input stream consisting of butted together variable length codewords. The length of the received fixed-length symbol is chosen to be less than the maximum codeword length. Each of these samples is used to derive an address defining a location in a memory where an indication of the decoded output symbol is stored along with an indication of the actual length of the codeword corresponding to the output symbol. The decoding apparatus includes a memory hierarchy which includes a primary table and a plurality of secondary tables for storing the information of the N-symbol alphabet table. The received fixed-length bit string is first compared with the primary table for a determination of a codeword. If a codeword is not found, then the bit string is compared with the bit patterns included in the secondary tables.
By the use of the memory hierarchy including the primary and the secondary tables, Frank's decoder is able to reduce the memory required to carry out the variable length decoding. The memory used for storing the alphabet table is smaller with the use of the primary and secondary tables. However, since the shift transfer from the input register is executed by a fixed sequence of clock signals, Frank's decoder suffers a major disadvantage that the operation speed of the decoder is too slow for a modern system implementation. The shift operation alone would take up several clock cycles which would be totally unacceptable for the purpose of modern high speed data processing.
Sun et al. discloses in another U.S. Pat. 5,173,695 entitled `High Speed Flexible Variable Length Decoder` (issued on Dec. 22, 1992) a variable length decoder which receives a bit stream into a buffer first. The decoder then reads out in parallel sequences equal in length to the maximum length codeword. These sequences of fixed length bit-strings are then read into cascaded latches. The cascaded sequences in both latches are input to a barrel shifter which provides from its multiple bit input, a sliding decoding window to a table-lookup memory device. A control signal directly shifts the position of the decoding window of the barrel shifter as each codeword is detected. To detect each codeword, the initial bits in the decoding window are compared with the codeword entries in the table lookup memory. when a codeword is detected, the corresponding stored codeword length is accumulated with previously accumulated codeword lengths to produce the control signal which directly shifts the decoding window by the number of bits in the decoded word. When all the bits in the first latch have been decoded, the next bit sequence in the buffer is input to the second latch while the previous bit sequence in the second latch is transferred to the first latch. The decoding window is then adjusted to the beginning of the next uncoded sequence.
Even that the decoder as disclosed by Sun et al. provides a faster decoding process wherein the detection of a code word is carried by comparing a plurality bits read into the first latch and that stored in the table-lookup memory in every time cycle, the decoder as disclosed by Sun et al. suffers the disadvantage that the lookup table memory for storing all the codewords may becomes quite large and occupies a large amount of memory space when the maximum length of the codeword becomes a great number.
Furthermore, the Barrel shifter used by Sun et al. has to handle the shift of a maximum number of bits up to M bits, i.e., the maximum length of the codeword. Again if the maximum length of the codeword becomes large, the hardware used to implement the Barrel shifter as that used by Sun would become quite voluminous. As it will explained below, the size of a Barrel Shifter is proportional to M.sup.2. It would become a major hindrance in reducing the size of the decoder for its implementation in a portable communication or computing apparatus.
Therefore, there is still a need in the art of variable length decoding to provide an apparatus and method such that the decoding process can be expeditiously performed with high speed in order to satisfy the real time data processing requirements. Meanwhile, for variable length decoding which involves codewords of greater length, there is a need to reduce the memory requirement and the circuit complexity whereby the decoder can be conveniently and economically employed in a more efficient manner to broader variety of applications.